
//Key - value模型
public class HashBuck {
    static class Node{
        public int key;
        public int val;//key的个数
        public Node next;
        public Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;//定义一个node类型的数组
    public int usedSize;//计算放入的元素
    public static final double loadFactor = 0.75;//定义哈希表的负载因子

    public HashBuck() {
        array = new Node[8];//给数组初始化
    }
    //向哈希表中插入数据（头插法）
    public void put(int key,int val){
        int index = key % array.length;//计算出当前数据的在数组当中的位置
        Node cur = array[index];//当index位置是一个链表的时候，定义一个cur结点遍历链表
        //当cur为空的时候，不进入循环
        while(cur != null){
            if(cur.key == key){//在链表当中找到于插入数据相同的数据时
                cur.val = val;//由于是key-value模型，所以更新value的值为插入结点的value值
                return ;
            }
            //如果没有找到，则继续向下找，知道将链表遍历完
            cur = cur.next;
        }
        //当链表当中没有与插入数据相同的数据，则建立一个结点，它的值为要插入的数据，value同样
        Node node = new Node(key,val);
        node.next = array[index];//先将链表的头节点链接在新结点的地址域
        array[index] = node;//然后将node结点放在数组index位置。
        usedSize++;//数组当中数据个数+1
        if(calculateLoadFactor() >= loadFactor){
            //扩容
            resize();
        }
    }
    //计算负载因子
    private double calculateLoadFactor(){
        return usedSize*1.0 /array.length;//乘以1.0的原因是，usedSize是整数类型的，计算出来之后是整数，这里我们需要小数。
    }
    private void resize(){
        Node[] newArray = new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[1];
            while(cur != null){
                Node curNext = cur.next;//创建一个curNode类型的变量，用来记录cur遍历到的结点的下一个位置
                int index = cur.key % newArray.length;//计算出cur遍历到的结点的在新数组中的位置
                cur.next = newArray[index];//采用头插法，将新数组的index位置的结点链接在新节点的地址域
                newArray[index] = cur;//再将结点链接在新的数组的index位置。
                cur = curNext;//将cur遍历到的结点放到新的数组当中之后，cur回到原来的数组的链表当中，遍历下一个结点
            }
        }
        array = newArray;//重新计算哈希之后，将数据全部插入新的数组之后，再将newArray
    }
    //通过查找key,返回value
    public int get(int key){
        int index = key % array.length;//计算key在哈希表当中的位置
        Node cur = array[index];//定义cur遍历index位置的链表
        while(cur != null){//将链表遍历完，不进入
            if(cur.key == key){//当cur遍历到的结点的值等于key
                return cur.val;//返回cur结点的value值
            }
            //若不相同，则继续向后遍历，直到将链表遍历完成
            cur = cur.next;
        }
        //将链表遍历完成还是没有找到，则返回-1
        return -1;
    }
}
